package xyz.scootaloo.oj.leetcode

import org.junit.Test
import xyz.scootaloo.common.TestDsl

/**
 * @author flutterdash@qq.com
 * @since 2021/7/9 15:43
 */
class P121 : TestDsl {

    /**
     * #
     * #       #
     * #   #   #
     * #   #   # #
     * #   # # # #
     * #   # # # #
     * # # # # # #
     */
    private fun maxProfit(prices: IntArray): Int {
        val sortedList = ArrayList<Int>()
        sortedList.add(prices[0])

        var max = 0
        for (i in 1 until prices.size) {
            val num = prices[i]
            if (num > sortedList.last()) {
                val current = num - sortedList.first()
                if (current > max)
                    max = current
            } else {
                while (sortedList.isNotEmpty() && sortedList.last() > num)
                    sortedList.removeLast()
                sortedList.add(num)
            }
        }

        return max
    }

    @Test
    fun test0() {
        maxProfit(intArrayOf(7, 1, 5, 3, 6, 4)) shouldBe 5
        maxProfit(intArrayOf(7, 6, 4, 3, 1)) shouldBe 0
    }

}
